/**
 * 该二叉树结构:
 *               10
 *             /   \
 *           8      19
 *         /      /   \
 *      '7'      15    22
 *     /             /
 *   6             20
 *
 * 插入原始值节点：
 * 假设插入7节点时:
 * 1.它从父节点开始比对，7 < 10，往下排在左子树
 * 2.跟子节点8比对，7 < 8，往下排
 * 3.跟子节点6比对，7 > 6，把6往下挤到左子树，7排到6原来位置
 *
 * 插入引用值节点：
 * 假设插入一个对象节点时，根据用户传入的排序函数进行比对
 *
 * BST二叉树结构：
 * BST {
 *   root: {
 *     elem: 10,
 *     parent: null,
 *     left: Node {elem: 8, parent: Node, left: Node, right: null},
 *     right: Node {elem: 19, parent: Node, left: Node, right: Node}
 *   },
 *   size: 7
 * }
 *
 * 树的遍历分为：
 * 1.前序遍历(先序遍历): 先访问根节点，然后左子树，然后右子树
 * 2.中序遍历：先左子树，再根节点，再右子树
 * 3.后序遍历：先左子树，再右子树，再根子树
 * 4.层序遍历：按照树的层级逐层至上而下遍历所有节点
 */

//节点的类
class Node {
  constructor(elem, parent) {
    this.elem = elem; //节点
    this.parent = parent; //父节点
    this.left = null; //左子树
    this.right = null; //右子树
  }
}

//二叉树的类
class BST {
  constructor(sortFn) {
    this.root = null; //根元素
    this.size = 0; //长度指的是所有子节点的个数
    this.sortFn = sortFn || this.sortFn; //接收一个用户定义的排序函数作为参数，没有时为BST类定义的函数
  }

  /**
   * 添加数组节点成员至二叉树里
   * @param {*} elem
   */
  add(elem) {
    //根节点为空时
    if (this.root === null) {
      //创造新的节点作为根节点
      this.root = new Node(elem, null);
      this.size++;
      return;
    } else {
      //不是根节点时

      //找到并定义根节点
      let currentNode = this.root;
      //初始化根节点(父节点)
      let parent = null;
      //初始化比对
      let compareRes = 0;

      //一直循环  直到找不到下层父节点就中止循环
      while (currentNode) {
        //对应引用值如对象时 使用排序函数来进行比对
        compareRes = this.sortFn(elem, currentNode.elem);
        // console.log(compareRes, elem, currentNode.elem);

        //当前节点与父节点对比
        // compareRes = elem - currentNode.elem;

        //重新定义根节点
        parent = currentNode;

        //判断当前插入节点对比父节点
        if (compareRes > 0) {
          //排在右子树上并作为下层的父节点
          currentNode = currentNode.right;
        } else {
          //排在左子树上并作为下层的父节点
          currentNode = currentNode.left;
        }
      }

      // console.log(currentNode);

      //创建一个新的节点(非根节点)
      let newNode = new Node(elem, parent);

      //当当前节点比父节点大时
      if (compareRes > 0) {
        //将当前节点排放到右子树上
        parent.right = newNode;
      } else {
        //将当前节点排放到左子树上
        parent.left = newNode;
      }

      this.size++;
    }
  }

  /**
   * BST类默认的排序函数
   * @param {*} a
   * @param {*} b
   * @returns
   */
  sortFn(a, b) {
    return a - b;
  }

  /**
   * 前序遍历(先序遍历): 先访问根节点，然后左子树，然后右子树
   * 括号为遍历节点的顺序
   * 应用场景是DOM遍历，深度遍历优先原则
   *              10(1)
   *             /   \
   *          8(2)   19(4)
   *         /      /   \
   *       6(3)   15(5)  22(6)
   *                    /
   *                  20(7)
   */
  preorderTraversal(visitor) {
    //用户必须传入一个对象否则阻止程序向下执行
    if (visitor === null) return;
    //先打印根节点再递归打印当前节点左子树和右子树
    const traversal = (node) => {
      //中止递归条件
      if (node === null) return;

      //打印根节点
      visitor.visit(node.elem);
      //打印当前节点左子树
      traversal(node.left);
      //打印当前节点右子树
      traversal(node.right);
    };

    //从根节点开始
    traversal(this.root);
  }

  /**
   * 中序遍历：先左子树，再根节点，再右子树
   * 可以看出节点大小是从小到大
   *              10(3)
   *             /   \
   *          8(2)   19(5)
   *         /      /   \
   *       6(1)   15(4)  22(7)
   *                    /
   *                  20(6)
   */
  inorderTraversal(visitor) {
    //用户必须传入一个对象否则阻止程序向下执行
    if (visitor === null) return;
    const traversal = (node) => {
      //中止递归条件
      if (node === null) return;

      //先打印当前节点左子树
      traversal(node.left);
      //打印根节点
      visitor.visit(node.elem);
      //后打印当前节点右子树
      traversal(node.right);
    };

    //从根节点开始
    traversal(this.root);
  }

  /**
   * 后序遍历：先左子树，再右子树，再根子树
   * 先找所有的子树，先操作子节点再操作父节点场景是文件目录
   *              10(7)
   *             /   \
   *          8(2)   19(6)
   *         /      /   \
   *       6(1)   15(3)  22(5)
   *                    /
   *                  20(4)
   */
  postorderTraversal(visitor) {
    //用户必须传入一个对象否则阻止程序向下执行
    if (visitor === null) return;
    const traversal = (node) => {
      //中止递归条件
      if (node === null) return;

      //先打印当前节点左子树
      traversal(node.left);
      //后打印当前节点右子树
      traversal(node.right);
      //打印根节点
      visitor.visit(node.elem);
    };

    //从根节点开始
    traversal(this.root);
  }

  /**
   * 层序遍历：按照树的层级逐层至上而下遍历所有节点
   * 符合广度遍历优先原则
   *              10(1)
   *             /   \
   *          8(2)   19(3)
   *         /      /   \
   *       6(4)   15(5)  22(6)
   *                    /
   *                  20(7)
   */
  levelOrderTraversal(visitor) {
    //用户必须传入一个对象否则阻止程序向下执行
    //第一层父节点没有时不往下执行
    if (this.root === null || visitor === null) return;

    //定义一个数组保存每层遍历的节点
    let arr = [this.root];
    //初始化数组元素索引
    let index = 0;
    //初始化当前节点
    let currentNode = null;

    //一直循环直到
    while ((currentNode = arr[index++])) {
      //打印根节点
      visitor.visit(currentNode.elem);

      //左子树有值时
      if (currentNode.left) {
        //存入当前节点
        arr.push(currentNode.left);
      }
      //右子树有值时
      if (currentNode.right) {
        //存入当前节点
        arr.push(currentNode.right);
      }
    }
  }

  /**
   * 遍历树的时候，先把树反转一下
   *              10()                               10()
   *             /   \                               /   \
   *          8()   19()                         19()    8()
   *         /      /   \                        /   \      \
   *       6()   15()  22()         ->        22()   15()   6()
   *                    /                        \
   *                  20()                       20()
   */
  invertTree() {
    //反转树是在遍历树的基础上

    //第一层父节点没有时不往下执行
    if (this.root === null) return;

    //定义一个数组保存每层遍历的节点
    let arr = [this.root];
    //初始化数组元素索引
    let index = 0;
    //初始化当前节点
    let currentNode = null;

    //一直循环直到
    while ((currentNode = arr[index++])) {
      //进行反转
      let temp = currentNode.left;
      currentNode.left = currentNode.right;
      currentNode.right = temp;

      //左子树有值时
      if (currentNode.left) {
        //存入当前节点
        arr.push(currentNode.left);
      }
      //右子树有值时
      if (currentNode.right) {
        //存入当前节点
        arr.push(currentNode.right);
      }
    }

    return this.root;
  }
}

//数组形式创建一个二叉树(原始值)
let arr1 = [10, 8, 6, 19, 15, 22, 20];
//数组形式创建一个二叉树(引用值)
let arr2 = [
  { name: 'Rose', age: 10 },
  { name: 'Jack', age: 8 },
  { name: 'Jessie', age: 6 },
  { name: 'Lulu', age: 19 },
  { name: 'Icy', age: 15 },
  { name: 'Kason', age: 22 },
  { name: 'Kason', age: 20 }
];

// 原始值写法：
// let bst = new BST();
// arr1.forEach((item) => {
//   bst.add(item);
// });

//引用值写法：
let bst = new BST((a, b) => a.age - b.age);

arr2.forEach((item) => {
  bst.add(item);
});

console.log(bst);
console.log(bst.root);

//传入对象的写法是访问者模式，给用户提供接口来获取当前数据，相当于控制中转
// bst.levelOrderTraversal({
//   visit(node) {
//     console.log(node);
//   }
// });

console.log(bst.invertTree());
